package com.yin.myproject.arithmetic;

import java.util.Arrays;

/**
 * 快速排序
 * @author Eason
 * @create 2018-04-22 10:05
 **/
public class QuickSorter {
    public static final int count = 0;

    public static void main(String[] args) {
        int array[] = {94, 12, 34, 76, 26, 9, 0, 37, 55, 76, 37, 5, 68, 83, 90, 37, 12, 65, 76, 49};
        QuickSorter sorter = new QuickSorter();
        int[] sort = sorter.sort(array, 0, array.length-1);
        System.out.println(Arrays.toString(sort));
    }

    private int[] sort(int[] array, int low, int high) {
        int pivotPos; // 划分基准元素索引
        if (low < high) {
            pivotPos = partition(array, low, high);
            sort(array, low, pivotPos - 1); // 左划分递归快速排序
            sort(array, pivotPos + 1, high); // 右划分递归快速排序
        }
        return array;
    }

    private int partition(int[] array, int i, int j) {
        Integer pivot = (array[i] + array[j]) >> 2; // 初始基准元素，如果quickSort方法第一次调用，pivot初始为数组第一个元素
        System.out.println("基准元素:" + pivot + ":" + i);
        while (i < j) { // 两个指针从两边向中间靠拢，不能相交
            // 右侧指针向左移动
            while (j > i && array[j] >= pivot) {
                j--;
            }
            if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[j] >= 基准元素pivot
                array[i] = array[j]; // 基准元素放到了j指针处
                i++; // 左侧i指针需要向右移动一个位置
            }
            // 左侧指针向右移动
            while (i < j && array[i] <= pivot) {
                i++;
            }
            if (i < j) { // 如果在没有使指针i和j相交的情况下找到了array[i] <= 基准元素pivot
                array[j] = array[i]; // 基准元素放到了i指针处
                j--; // 右侧j指针需要向左移动一个位置
            }
        }
        array[i] = pivot; // 将基准元素放到正确的排序位置上
        System.out.println("排序后的数组:" + Arrays.toString(array));
        return i;
    }
}
